#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

int nthUglyNumber(int n) {
    vector<int> f(n + 1);
    f[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;
    for (int i = 2; i <= n; i++)
    {
        int num2 = f[p2] * 2, num3 = f[p3] * 3, num5 = f[p5] * 5;
        f[i] = min(num2, min(num3, num5));
        if (f[i] == num2)    p2++;
        if (f[i] == num3)    p3++;
        if (f[i] == num5)    p5++;
    }
    return f[n];
}